package main

import "sort"

type MountainArray struct {
	arr []int
}

func (this *MountainArray) get(index int) int {
	return this.arr[index]
}

func (this *MountainArray) length() int {
	return len(this.arr)
}

func searchInLeft(target int, pivotIndex int, mountainArr *MountainArray) int {
	left := 0
	right := pivotIndex
	for left <= right {
		mid := left + (right-left)/2
		midV := mountainArr.get(mid)
		if target == midV {
			return mid
		} else if target > midV {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func searchInRight(target int, pivotIndex int, mountainArr *MountainArray) int {
	left := pivotIndex + 1
	right := mountainArr.length() - 1
	for left <= right {
		mid := left + (right-left)/2
		midV := mountainArr.get(mid)
		if target == midV {
			return mid
		} else if target > midV {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

func findInMountainArray(target int, mountainArr *MountainArray) int {
	peekIndex := sort.Search(mountainArr.length()-1, func(i int) bool {
		return mountainArr.get(i) > mountainArr.get(i+1)
	})
	peek := mountainArr.get(peekIndex)
	if target == peek {
		return peekIndex
	} else if target > peek {
		return -1
	}
	// 搜索 [0, peekIndex)
	leftRet := searchInLeft(target, peekIndex, mountainArr)
	if leftRet != -1 {
		return leftRet
	}
	return searchInRight(target, peekIndex, mountainArr)
}

func main() {
	//println(findInMountainArray(3, &MountainArray{[]int{1,2,3,4,5,3,1}}))
	//println(findInMountainArray(3, &MountainArray{[]int{0,1,2,4,2,1}}))
	//println(findInMountainArray(3, &MountainArray{[]int{0,1,2,4, 3, 2,1}}))
	//println(findInMountainArray(3, &MountainArray{[]int{1, 2, 3, 5, 3}}))
	println(findInMountainArray(0, &MountainArray{[]int{1, 2, 3, 5, 3}}))

}
